package LearnDataStructure.f_并查集;

import java.util.HashSet;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 19:10
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.f_并查集
 */
public class UnionFindSet {

    /**
     * 查方法
     * @param source
     * @return
     */
    public static UnionFindNode find(UnionFindNode source) {
        UnionFindNode node = source;
        HashSet<UnionFindNode> path = new HashSet<UnionFindNode>();
        while (node.parent != null) {//顺着当前节点的父节点，一路找到root
            path.add(node);
            node = node.parent;
        }
        //跳出while后，node就是root
        //下面是重新认父，也就是减小树的高度
        for (UnionFindNode element : path) {//将循环中路过的所有的节点，的父亲，全部改成root
            element.parent = node;
        }
        return node;//root
    }

    /**
     * 并方法
     * @param parent
     * @param child
     */
    public static void union(UnionFindNode parent, UnionFindNode child) {
        find(child).parent = parent;
        /*
        find(child)的结果是返回当前并查集的root
        root的parent是null
        把parent当成了root的父节点
        所以说parent成为了新的root
         */
    }
}
